home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group94c.txt / 000021_icon-group-sender _Mon Dec 19 14:08:33 1994.msg < prev    next >
Internet Message Format  |  1995-02-09  |  5KB
  1. Received: by cheltenham.cs.arizona.edu; Mon, 19 Dec 1994 14:08:59 MST
  2. Date: Mon, 19 Dec 1994 14:08:33 +0700
  3. From: swampler@noao.edu
  4. Message-Id: <9412192108.AA04964@orpheus.gemini.edu>
  5. Subject: Re: Backtracking in Icon
  6. To: icon-group@cs.arizona.edu
  7. Content-Length: 4346
  8. Errors-To: icon-group-errors@cs.arizona.edu
  9.  
  10. Brandon Allbery wrote:
  11.  
  12. >> 
  13. >> I think the problem with general use of backtracking is that, while
  14. >> convenient, it's less efficient than improved algorithms are for any given
  15. >> task.  (Compare recursive vs. nonrecursive algorithms as another example.)
  16. >> Nevertheless, when it's needed (no readily available non-backtracking
  17. >> algorithm available in a timely fashion) backtracking is very useful.
  18. >> 
  19.  
  20. Undoubtably true.  However, if the speed of execution isn't particularly
  21. important (for example, if the program is interactive and likely to
  22. be dominated by the 'idle user loop'...), then backtracking solutions
  23. can be easy to implement *if* one is thinking that way.
  24.  
  25. The following code fragment is one that Ehud mentioned as an example of
  26. backtracking.  The original author is Dan Higdon (are you out there, Dan?),
  27. way back in '88.  I just added some additional features needed by the
  28. university I was at during that period.
  29.  
  30. It's the heart of a course scheduling application to let students work
  31. out schedules that suit their needs in an environment where there might
  32. be 10's and 100's of sections of some courses.
  33.  
  34. The algorithm is a bit daunting if you're not used to (1) Icon, (2) backtracking
  35. and (3) combining recursion with backtracking, but I think it's pretty
  36. straightforward given those constraints.  It takes out a class, schedules
  37. the remaining classes (that's the recursion), then tries to find a section
  38. of the 'deleted' class that fits in the student's schedule and meets a
  39. series of constraints {for example, the campus is 1.5 miles long, north to
  40. south (with a green belt in the middle), so the routine nonConflicting()
  41. includes a check for how much time there is between classes at opposite
  42. ends of campus.  It also checks to see if there is room in the class, etc.
  43.  
  44. If the class cannot be scheduled or the schedule is rejected by the student
  45. running the program, then the algorithm backtracks to try another section
  46. of the previous class.  (and so on...)  Oh yes, for classes with required
  47. labs, it automatically adds those to the schedule as well.
  48.  
  49. Enough of that, here's the heart of the algorithm:
  50.  
  51. --------------------------------------------------------------------------------
  52. # In order to preserve the backtracking idea, schedule is
  53. # a generator which generates the possible schedules at
  54. # that level of recursion.
  55. #
  56. # clist is a list of class names
  57. #
  58. # The algorithm is as follows:
  59. # If clist is null, fail
  60. # otherwise,
  61. #    Generate every remaining schedule and do the following with each:
  62. #       get the class name
  63. #       Generate every non-null and unconflicting time for each class and
  64. #          insert it into the set
  65. #          suspend this schedule, then delete the entry
  66. #
  67. procedure schedule (cs)
  68.    local t, schedl, class, tlab
  69.  
  70.    if *cs = 0 then return cs    # end the recursion, the set of classes is done
  71.  
  72.    delete(cs,class := ?cs)    # randomly pick out a class...
  73.                                 #   then schedule all the others
  74.                 #    before fitting this one in.
  75.    every schedl := schedule(cs) &
  76.          freespace(t := !classdb[class]) & 
  77.          nonConflicting(t, schedl) &
  78.          (/t.lab | nonConflicting(tlab <- !\t.lab,schedl))
  79.       do {                     # Got it!  Put it (and lab) into schedule
  80.          suspend set([t, \tlab] | [t])\1 ++ schedl
  81.          }
  82. end
  83. -------------------------------------------------------------------------------
  84.  
  85. If you've lasted this long, give the program a try...telnet to
  86.  
  87.     pine.cse.nau.edu
  88.  
  89. and login in as 'sch'. You'll need an ANSI compatible terminal
  90. to see the schedules themselves. 
  91.  
  92. Try the command 'help', then (say) 'help new'.
  93. You can get a list of classes in a department by using the 'courses'
  94. command, e.g.
  95.  
  96.     courses cse
  97.  
  98. will list all the courses offered by the Computer Science and Engineering
  99. department.
  100.  
  101.     courses cse4
  102.  
  103. will list all the 400-level (senior) courses.  (So Icon devotees will
  104. immediately infer that match() is used to look up courses, and yes,
  105.  
  106.     courses ""
  107.  
  108. will list every course offered at the university (I hope you have a *fast*
  109. connection!.)  Do the school a favor and don't print out any schedules!
  110.  
  111. --
  112. Steve Wampler - swampler@gemini.edu [Gemini 8m Telescopes Project (under AURA)]
  113. --
  114. The Gods that were smiling when you were born are laughing now.
  115.                       -- found in a fortune cookie